/**
 * 35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请**必须使用**时间复杂度为 O(log n) 的算法。



示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:

输入: nums = [1], target = 0
输出: 0


提示:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为**无重复元素**的升序排列数组
-10^4 <= target <= 10^4
 *
 */

#include <iostream>
#include "vector"
using namespace std;
int searchInsert(vector<int> &nums, int target);
int outputNums(vector<int> &nums);

int main(void)
{
  vector<int> v = {1, 3, 5, 6};
  int target = 5; // 2
  // vector<int> v = {1, 3, 5, 6};
  // int target = 2;// 1 insert
  // vector<int> v = {1, 3, 5, 6};
  // int target = 7; // 4 insert
  // vector<int> v = {1, 3, 5, 6};
  // int target = 0; // 0 insert
  // vector<int> v = {1};
  // int target = 0;// 0 insert
  // vector<int> v = {1};
  // int target = 1;// 0

  // vector<int> v = {1, 3};
  // int target = 2; // 1 insert

  int res = searchInsert(v, target);
  cout << "res: " << res << endl;

  outputNums(v);

  return 0;
}

int outputNums(vector<int> &nums)
{
  vector<int>::iterator ite = nums.begin();
  while (ite != nums.end())
  {
    cout << *ite << " " << endl;
    ite++;
  }
}

/**
int searchInsert(vector<int> &nums, int target)
{
  int low = 0;
  int high = nums.size() - 1;
  while (low < high)
  {
    int mid = low + (high - low) / 2;
    int num = nums[mid];
    if (num == target)
    {
      return mid;
    }
    else if (num < target)
    {
      low = mid + 1;
    }
    else
    {
      high = mid - 1;
    }
  }

  // 左右区间端点合并 low == high
  if (target == nums[low])
  {
    return low;
  }
  else if (target > nums[low])
  {
    // 中间数是较小那个 该数必定是插末尾，但保险用insert
    vector<int>::iterator ite = nums.begin() + low + 1;
    ite = nums.insert(ite, target);

    // return low + 1;
    // return (int)distance(nums.begin(), ite);// 迭代器->索引
    // return (int)(ite - nums.begin());// 迭代器->索引
    return ite - nums.begin(); // 迭代器 -> 索引
  }
  // target < nums[low]
  else
  {
    // vector<int>::iterator ite = nums.begin() + low;
    vector<int>::iterator ite = nums.begin();
    advance(ite, low);
    ite = nums.insert(ite, target);
    return (int)distance(nums.begin(), ite);// 迭代器->索引
    // return ite - nums.begin();

    // return low - 1 <= 0 ? 0 : (low - 1);// {1, 3} 2 有问题
  }
  // else
  // {
  //   // 中间数是较小那个 该数必定是插末尾，但保险用insert
  //   vector<int>::iterator ite = nums.begin() + high + 1;
  //   nums.insert(ite, target);

  //   return high + 1;
  // }
}
*/

/**
// 官方题解<视频题解、算法总结>
int searchInsert(vector<int> &nums, int target)
{
  int left = 0;
  int right = nums.size() - 1;
  while (left <= right)
  {
    // int mid = (right - left) / 2 + left;
    int mid = ((right - left) >> 1) + left;
    int num = nums[mid];
    if (num == target)
    {
      return mid;
    }
    else if (num < target)
    {
      left = mid + 1;
    }
    else
    {
      right = mid - 1;
    }
  }

  nums.insert(nums.begin() + left, target);
  return left; // 二分循环结束时未查到结果，left就为插入位置
}
*/

// 官方实例代码
int searchInsert(vector<int> &nums, int target)
{
  int n = nums.size();
  int l = 0, r = n - 1;
  int ans = n; // mid二分偶数时取的是中间较小的那个数，mid一直比tar大必是在末尾添加一个数
  while (l <= r)
  {
    int m = ((r - l) >> 1) + l;
    if (nums[m] >= target)
    {
      ans = m;
      r = m - 1;
    }
    else
    {
      l = m + 1;
    }
  }
  return ans;
}